public class CanibaliMisionari
{  static boolean already[][][] = new boolean[4][][];
   static State pred[][][] = new State[4][][];
   static int d[][][] = new int[4][][];
   static int infinity = 20000;
   
   static int go(State s)
   {
      System.out.println("Incearca " + s.m + s.c + (s.b == 0 ? 'L' : 'R'));
      already[s.m][s.c][s.b] = true;
      if(s.m == 0 && s.c == 0 && s.b == 1)
          { d[0][0][1] = 0;
            return 0;  
          }
      
      int i,j;
      int ans = infinity;
      int z;
      State t;
	  
      for(i=0;i<=2;i++) for(j=0;j<=2;j++)
         { if(i+j == 0) continue;
           if(i+j > 2) continue;
           t = s.move(i,j);
           if(! t.legal()) continue;
           if(already[t.m][t.c][t.b])
              z = d[t.m][t.c][t.b];
           else
              z = go(t);
           if(z < ans)
              { ans = z;
                pred[t.m][t.c][t.b] = s;
              }
         }
      
       System.out.println("Revenind " + ans + " du-te la ");
       if(ans < infinity)
          { d[s.m][s.c][s.b] = ans + 1;
            return ans + 1;
          }
       else
          return infinity;
     }
  

   public static void main(String args[])
   { 
     int i,j,k;
     for(i=0;i<4;i++)
     { already[i] = new boolean[4][];
       d[i] = new int[4][];
       pred[i] = new State[4][];
       for(j=0;j<4;j++)
          { already[i][j] = new boolean[2];
            d[i][j] = new int[2];
            pred[i][j] = new State[2];
            for(k=0;k<2;k++)
               { already[i][j][k] = false;
                 pred[i][j][k] = new State();
                 d[i][j][k] = infinity;
               }
          }
       }
       State start = new State(); 
       int ans = go(start);
       if(ans == infinity)
          { System.out.println("Nu exista o solutie.");
           
            return;
          }
       System.out.println("Succes:  este nevoie de " + ans + " puncte de trecere.");
       State q = new State();
       q.m = 0; q.c = 0; q.b = 1; 
       State[] solution = new State[ans+1];
       solution[ans] = q;
       for(i=ans-1;i>=0;i--)
          { solution[i] = pred[q.m][q.c][q.b];
            q = solution[i];
          }
       for(i=0;i<ans;i++)
          solution[i].display();
    }
}